package tree;

/**
 * @author : Rookie
 * @description : 满二叉树的节点数量
 * @date : 2023/10/13
 */
public class FullBinaryTreeLeaf {

    public static void main(String[] args) {
        int[] input = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        TreeNode root = BinaryTreeUtil.buildTree(input);
        System.out.println(getNum1(root));
        System.out.println(getNum2(root));
    }

    /**
     * 普通遍历写法
     * @param root
     * @return
     */
    private static int getNum1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftNodes = getNum1(root.left);
        int rightNodes = getNum1(root.right);
        return leftNodes + rightNodes +1;
    }

    /**
     * 用完全二叉树的特性求
     * @param root
     * @return
     */
    private static int getNum2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0,rightDepth = 0;
        while (left != null) {
            left = left.left;
            leftDepth++;
        }
        while (right != null) {
            right = right.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            // 遍历到最后，就算只有1个节点也是满二叉树
            return (2 << leftDepth) - 1;
        }
        int leftNodes = getNum2(root.left);
        int rightNodes = getNum2(root.right);
        return leftNodes+rightNodes+1;
    }
}
